package tree.递归;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N验证二叉树的前序序列化331.java
 * @Description https://leetcode-cn.com/problems/verify-preorder-serialization-of-a-binary-tree/
 * @createTime 2021年04月21日 13:05:00
 */
public class N验证二叉树的前序序列化331 {

    /**
     * 叶子节点后面的两个节点必定是
     *      4
     *    /   \
     *   #     #
     * 非叶子节点后面的两个节点是
     *       4
     *     /   \
     *    #     2
     * 或者
     *      4
     *    /   \
     *   1     2
     * 只有这三种情况。
     *
     * 可以吧 4 # # 这种情况也看成是一个叶子节点 也就是 4 #  #  --->  #
     * 如输入： "9,3,4,#,#,1,#,#,2,#,6,#,#" ，当遇到 x,#,# 的时候，就把它变为 #。
     *[9,3,4,#,#,1,#,#,2,#,6,#,#] => [9,3,#,#,2,#,#] => [9,#,#]，=> [#]
     *
     */

        LinkedList<String> stack = new LinkedList<>();
        public boolean isValidSerialization(String preorder) {
        for (String str : preorder.split(",")) {
            stack.push(str);
            while (stack.size() >= 3
                && stack.get(0).equals("#")
                && stack.get(1).equals("#")
                && !stack.get(2).equals("#")
            ) {
                stack.pop();
                stack.pop();
                stack.pop();
                stack.push("#");
            }
        }
        return stack.size() == 1 && stack.pop().equals("#");
    }

    /**
     * 入度 出度
     *           3（0，2）
     *         /    \
     * （1，2）4      #（1，0）
     *      /   \   /  \
     （1，0)#    #（1，0)
     *
     * 只要把字符串遍历一次，每个节点都累加 diff = 出度 - 入度。在遍历到任何一个节点的时候，要求diff >= 0，原因是还没遍历到该节点的子节点，所以此时的出度应该大于等于入度。当所有节点遍历完成之后，整棵树的
     * diff == 0
     *
     *  diff 的初始化为 1。因为，我们加入一个非空节点时，都会对 diff 先减去 1（入度），再加上 2（出度）。但是由于根节点没有父节点，所以其入度为 0，出度为 2。因此 diff 初始化为
     *  1，是为了在加入根节点的时候，diff 先减去 1（入度），再加上 2（出度），此时 diff 正好应该是2.
     */
    public boolean isValidSerialization2(String preorder) {
        int diff=1;
        for (String str : preorder.split(",")) {
            //先减去入度
            diff--;
            //然后加上出度，非叶子节点出度为2，叶子节点为0，如果diff<0则不是完整的树
            if (diff < 0){
                return false;
            }
            if(!str.equals("#")){
                diff += 2;
            }
        }
        return diff==0;
    }

}
